package heap;

public class Heap<T extends Comparable<T>> {
    private T[] items;
    private int N;

    public Heap(int capacity) {
        items = (T[]) new Comparable[capacity + 1];
        N = 0;
    }

    /**
     * i 是否小于 j
     */
    private boolean less(int i, int j) {
        return items[i].compareTo(items[j]) < 0;
    }

    private void exchange(int i, int j) {
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    public void insert(T t) {
        items[++N] = t;
        swim(N);
    }

    /**
     * 上浮算法
     */
    private void swim(int k) {
        while (k != 1) {
            // 如果当前结点比其父节点大 则上浮
            if (less(k / 2, k)) {
                exchange(k / 2, k);
            }
            k = k / 2;
        }
    }

    public T delMax() {
        T max = items[1];
        // 将N处 于 1 交换
        exchange(1, N);
        // 清除N的元素
        items[N] = null;
        N--;
        // 进行下沉
        sink(1);
        return max;
    }

    private void sink(int k) {
        // 最底层边界 2*k>N
        while (2 * k <= N) {
            int max;
            // 如果存在右结点
            if (2 * k + 1 <= N) {
                // 选择左右结点中较大者
                if (less(2 * k, 2 * k + 1)) {
                    max = 2 * k + 1;
                } else {
                    max = 2 * k;
                }
            } else {
                // 只有左节点
                max = 2 * k;
            }
            if (less(max, k)) {
                // 如果较大结点比当前k小 那就退出
                break;
            }
            // 交换
            exchange(k, max);
            // 进行下一层下沉
            k = max;
        }
    }

    public static void main(String[] args) {
        Heap<String> heap = new Heap<>(20);
        heap.insert("S");
        heap.insert("G");
        heap.insert("I");
        heap.insert("E");
        heap.insert("N");
        heap.insert("H");
        heap.insert("O");
        heap.insert("A");
        heap.insert("T");
        heap.insert("P");
        heap.insert("R");
        String del;
        while ((del = heap.delMax()) != null) {
            System.out.print(del + ",");
        }
    }

}
